Recursive Calculation of Relative Convex Hulls
Identifieur interne : 002644 ( Main/Exploration ); précédent : 002643; suivant : 002645Recursive Calculation of Relative Convex Hulls
Auteurs : Gisela Klette [Nouvelle-Zélande]Source :
- Lecture Notes in Computer Science [ 0302-9743 ]
Abstract
Abstract: The relative convex hull of a simple polygon A, contained in a second simple polygon B, is known to be the minimum perimeter polygon (MPP). Digital geometry studies a special case: A is the inner and B the outer polygon of a component in an image, and the MPP is called minimum length polygon (MLP). The MPP or MLP, or the relative convex hull, are uniquely defined. The paper recalls properties and algorithms related to the relative convex hull, and proposes a (recursive) algorithm for calculating the relative convex hull. The input may be simple polygons A and B in general, or inner and outer polygonal shapes in 2D digital imaging. The new algorithm is easy to understand, and is explained here for the general case. Let N be the number of vertices of A and B; the worst case time complexity is ${\cal O}(N^2)$ , but it runs for “typical” (as in image analysis) inputs in linear time.
Url:
DOI: 10.1007/978-3-642-19867-0_22
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 001358
- to stream Istex, to step Curation: 001341
- to stream Istex, to step Checkpoint: 000544
- to stream Main, to step Merge: 002686
- to stream Main, to step Curation: 002644
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Recursive Calculation of Relative Convex Hulls</title><author><name sortKey="Klette, Gisela" sort="Klette, Gisela" uniqKey="Klette G" first="Gisela" last="Klette">Gisela Klette</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:539B9F2EE9372945FB8956BDA038E2DE79CD9AE5</idno><date when="2011" year="2011">2011</date><idno type="doi">10.1007/978-3-642-19867-0_22</idno><idno type="url">https://api.istex.fr/ark:/67375/HCB-4CM2W2H4-V/fulltext.pdf</idno><idno type="wicri:Area/Istex/Corpus">001358</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001358</idno><idno type="wicri:Area/Istex/Curation">001341</idno><idno type="wicri:Area/Istex/Checkpoint">000544</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000544</idno><idno type="wicri:doubleKey">0302-9743:2011:Klette G:recursive:calculation:of</idno><idno type="wicri:Area/Main/Merge">002686</idno><idno type="wicri:Area/Main/Curation">002644</idno><idno type="wicri:Area/Main/Exploration">002644</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Recursive Calculation of Relative Convex Hulls</title><author><name sortKey="Klette, Gisela" sort="Klette, Gisela" uniqKey="Klette G" first="Gisela" last="Klette">Gisela Klette</name><affiliation wicri:level="1"><country xml:lang="fr">Nouvelle-Zélande</country><wicri:regionArea>School of Computing & Mathematical Sciences, Auckland University of Technology, Private Bag 92006, 1142, Auckland</wicri:regionArea><wicri:noRegion>Auckland</wicri:noRegion></affiliation></author></analytic><monogr></monogr><series><title level="s" type="main" xml:lang="en">Lecture Notes in Computer Science</title><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: The relative convex hull of a simple polygon A, contained in a second simple polygon B, is known to be the minimum perimeter polygon (MPP). Digital geometry studies a special case: A is the inner and B the outer polygon of a component in an image, and the MPP is called minimum length polygon (MLP). The MPP or MLP, or the relative convex hull, are uniquely defined. The paper recalls properties and algorithms related to the relative convex hull, and proposes a (recursive) algorithm for calculating the relative convex hull. The input may be simple polygons A and B in general, or inner and outer polygonal shapes in 2D digital imaging. The new algorithm is easy to understand, and is explained here for the general case. Let N be the number of vertices of A and B; the worst case time complexity is ${\cal O}(N^2)$ , but it runs for “typical” (as in image analysis) inputs in linear time.</div></front></TEI><affiliations><list><country><li>Nouvelle-Zélande</li></country></list><tree><country name="Nouvelle-Zélande"><noRegion><name sortKey="Klette, Gisela" sort="Klette, Gisela" uniqKey="Klette G" first="Gisela" last="Klette">Gisela Klette</name></noRegion></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002644 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 002644 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:539B9F2EE9372945FB8956BDA038E2DE79CD9AE5
|texte= Recursive Calculation of Relative Convex Hulls
}}
| This area was generated with Dilib version V0.6.33. |  |